#include <stdio.h>
#include <stdlib.h>
#define INF 1000
void shortest_path_dijkstra() {

#define SIZE 6
	int graph[SIZE][SIZE] = {
	INF, INF, 10, INF, 30, 100,
	INF, INF, 5, INF, INF, INF,
	INF, INF, INF, 50, INF, INF,
	INF, INF, INF, INF, INF, 10,
	INF, INF, INF, 20, INF, 60,
	INF, INF, INF, INF, INF, INF };

	int i, j, k, v, src = 0;
	int currentMin[SIZE], final[SIZE] = { 0 }, path[SIZE][SIZE] = { 0 },
			order[SIZE];
	for (i = 0; i < SIZE; i++) {
		currentMin[i] = graph[src][i];
		if (currentMin[i] < INF) {
			path[i][src] = 1;		  //src,src到i的最短路径经过src节点
			path[i][i] = 1;
		}
	}
	final[src] = 1;
	currentMin[src] = 0;
	for (i = 1; i < SIZE; i++) {
		int min = INF;            //未被选定节点中，距src最近的距离
		for (j = 0; j < SIZE; j++) {
			if (final[j] != 1) {
				if (currentMin[j] < min) {
					v = j;
					min = currentMin[j];
				}
			}
		}
		final[v] = 1;             //选定距src最近的节点
		//更新未被选定节点，到src的最近距离
		for (j = 0; j < SIZE; j++) {
			if (final[j] != 1 && min + graph[v][j] < currentMin[j]) {
				currentMin[j] = min + graph[v][j];
				for (k = 0; k < SIZE; k++) {
					path[j][k] = path[v][k];
					path[j][j] = 1;
				}
			}
		}
	}
	for (i = 0; i < SIZE; i++) {
		printf("%d\t", currentMin[i]);
	}
}

void shortest_path_floyd() {
#define SIZE 3
	int graph[SIZE][SIZE] = {
			0, 4, 11,
			6, 0, 2,
			3, INF, 0 };

	int D[SIZE][SIZE];
	int path[SIZE][SIZE][SIZE]
	int v, w, u;
	for (v = 0; v < SIZE; v++) {
		for (w = 0; w < SIZE; w++) {
			D[v][w] = graph[v][w];
			if(graph[v][w] < INF) {
				path[v][w][v]=1;
				path[v][w][w]=1;
			}
		}
	}
	for (u = 0; u < SIZE; u++) {
		for (v = 0; v < SIZE; v++) {
			for (w = 0; w < SIZE; w++) {

				if (D[v][w] > D[v][u] + D[u][w]) {
					D[v][w] = D[v][u] + D[u][w];
					int i;
					for(i=0;i<SIZE;i++) {
						path[v][w][u] = path[v][u][i] || path[u][w][i];
					}
				}
				printf("%d\t", D[v][w]);
			}
			printf("\n");
		}
		printf("--------------------------------------\n");
	}
}

int main(void) {
	/*
	 //单源点最短路径
	 shortest_path_dijkstra();
	 */

	//每对节点之间的最短路径
	shortest_path_floyd();
	return 0;
}
